package com.zhn;

/**
 * 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
 *
 * 创建一个根节点，其值为 nums 中的最大值。
 * 递归地在最大值 左边 的 子数组前缀上 构建左子树。
 * 递归地在最大值 右边 的 子数组后缀上 构建右子树。
 * 返回 nums 构建的 最大二叉树 。
 */

public class ConstructMaximumBinaryTree {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        TreeNode treeNode = travelTree(nums, 0, nums.length-1);
        return treeNode;
    }

    public TreeNode travelTree(int[] nums,int left,int right){
        //递归到一个无效的区间（即 left>right）时，便可以返回一棵空的树
        if(left > right){
            return null;
        }
        int best = left;
        for(int i = left+1; i <= right; i++){
            if(nums[i] > nums[best]){
                best = i;
            }
        }
        TreeNode node = new TreeNode(nums[best]);
        node.left = travelTree(nums,left,best-1);
        node.right = travelTree(nums, best+1, right);
        return node;
    }
}
